1. Field of Invention
The present invention relates to a multi-color image encoding and/or decoding apparatus and its method. More particularly, the present invention relates to color order transformation of an index which is attached during encoding and decoding the multi-color image.
2. Description of Related Art
Multi-color images have been used in personal computers, game machines and the like. A multi-color image is also called a representative color image or a limited color image. As shown in FIG. 22, a multi-color image is an image in which an index is attached to a specific color, namely a color having a specific R(red), G(green) and B(blue) value, and using the index data to express the image by limited representative colors consisting of 16,256 colors.
This type of multi-color image data requires a total of 24 bits assuming that each of R, G, and B color is displayed by 8 bits (256 types). However, because an index is also displayed by 8 bits, the data compression rate is substantial. Despite the compression, the information volume is still very large, which makes the communication of data too slow to be practical if the data is processed without any change. Hence, compression technology of multi-color images is extremely important. A multi-color image requires encoding and decoding compression technology (i.e., a reversible compression technology) without loss because the number of colors is limited for a multi-color image.
A technology based on an entropy encoder and decoder has drawn attention in recent years as one type of data compression technique. An example of such is a technology which uses an arithmetic encoding and decoding technology. Synopsis of this technology is described in Japanese Laid-Open Patent Publication 62-185413, Japanese Laid-Open Patent Publication 63-74324 and Japanese Laid-Open Patent Publication 63-76525, the subject matters of which are incorporated herein by reference.
FIGS. 16(A)-(B) show a conventional multi-color encoding system 50 and decoding system 60 which use the above technology. The encoding system 50 includes a line buffer 51 and an entropy encoder 52. Color pixel data 100A is input to the line buffer 51 and the entropy encoder 52. All the color pixel data 100A (shown in FIG. 17) is raster scanned and sequentially input as pixel data in the order of horizontal scanning. A method of attaching an index in the order of the input color is used as a method to form the index data (i.e., the color pixel data 100A) which creates a phenomena such that the colors are substantially different for data with close index such as "1" and "2" or that the colors are quite close for the data with large differences in index such as "100" and "200" as shown in FIG. 22. A method to avoid such phenomena by attaching successive numbers to similar colors is disclosed in Japanese Laid-Open Patent Publication 5-328142, the subject matter of which is incorporated herein by reference.
The line buffer 51 is a reference pixel generation device that generates reference pixel data A, B, C and D for encoding the target pixel X (from the input color pixel data 100A). In other words, the line buffer 51 stores the chronology of n lines (usually 1 to 5 lines) when scanning the image. Moreover, each time the color pixel data 100A is input, the line buffer 51 outputs a series of pixel data to the entropy encoding device 52 consisting of the most recently input pixel A and surrounding pixels B, C and D as reference pixel data 110.
The entropy encoding device 52 uses an arithmetic encoding or Huffman encoding technique. The entropy encoder 52 uses the reference pixel data 110 as status signals, transforms the color pixel data 100A into encoding data 200 and outputs the same.
On the other hand, the decoding system 60 includes a line buffer 61 and an entropy decoder 62. The line buffer 61 and the entropy decoder 62 are created such that the input encoding data 200 is decoded and output through a reverse procedure than that taken by the line buffer 51 and the entropy encoder 52 of the encoding system 50.
The encoding system 50 and the decoding system 60 use completely reversible algorithms to encode the color pixel data 100A into encoding data 200, and to decode the encoding data 200 into the color pixel data 100B. This system is widely used in a variety of applications.
However, when the value or index number of the color pixel data 100A approaches a certain number, the data compression rate improves. The reference pixel data 110 is used as a status signal of the entropy encoder 52 and the entropy decoder 62. Hence, by taking a large number of status numbers (i.e., the reference pixel data) the data compression rate improves. In other words, in structuring the entropy encoder 52 and the entropy decoder 62 using an arithmetic encoding or Huffman encoding technique, the data compression rate may be drastically improved by making large disparity in the occurrence probabilities of the symbols 0 or 1. This is because the entropy encoding technique assigns short encoding data to input data with a high occurrence probability while it assigns relatively long encoding data to input data with a low occurrence probability.
In order to obtain large disparity in the occurrence probability of symbols (i.e., index numbers) a method has been used in which the input data is classified into several statuses and encoded. This is because an improved compression rate is not obtained unless the data is classified. For example, in a conventional technology such as shown in FIGS. 16(A)-(B), reference pixel data is created using the line buffers 51, 61 and is input in the entropy encoder 52 and the entropy decoder 62 as status signals to be used for classification. The entropy encoder 52 and the entropy decoder 62 classify the input data using the status signals and execute encoding and/or decoding. In other words, the entropy encoder 52 and the entropy decoder 62 compute the occurrence probability of each state of the reference pixel data and assign short encoding data to the combination of data with the higher occurrence probability. This improves the data compression rate.
However, a number of encoding parameter tables corresponding to the number of status of the reference pixel data is necessary for the entropy encoder 52 and the entropy decoder 62. The larger the number of reference pixel data, the larger the parameter tables for encoding and decoding. Hence, the entropy encoder 52 and the entropy decoder 62 become large in size and more expensive.
For example, suppose that the color pixel data, namely, the index number includes a 4 bit data (16 types), and the number of pixels of the reference pixel data 110 is four. In this case, the number of status of the encoding and the decoding parameter tables becomes 4 pixels.times.4 bit=16 status per bit, namely 2.sup.16 numbers of status. Hence, a parameter table for 2.sup.16 =65536 entries must be prepared. This shows that an increase in reference pixels results in a large number of encoding and decoding tables which causes the hardware (i.e., the entropy encoder 52 and the entropy decoder) to become large. Moreover, because the target pixel is composed of 4 bits, and because a one bit signal is assigned to each plane, resulting in 16 entries of colors for 4 bits, which in turn requires the parameter table to become a table of 65536.times.16 as shown in FIG. 18.
Japanese Laid-Open Patent Publication 6-276041, the subject matter of which is incorporated herein by reference, describes a method of color order transformation in which the disparity of occurrence frequency of color symbols for the target pixel is computed and the index number is rearranged corresponding to the occurrence frequency order. The compression rate is further increased by assigning a short encoding data to the index number with a high occurrence frequency. Japanese Laid-Open Patent Publication 6-276041 also discloses a technology in which a parameter table is made smaller in the entropy encoder 52 and the entropy decoder 62 according to the degenerated status number.
FIGS. 19(A)-(B) show the system of degenerating the number of status 15 disclosed in Japanese Laid-Open Patent Publication 6-276041 where the status signal 140 is generated by the status degenerating equipment 53, 63 which degenerates the reference pixel data 110 being output from the line buffer when the reference pixel data 110 is input as the status signal into the entropy encoder 52 and the entropy decoder 62. This input is the same as in the conventional encoding system 50 and decoding system 60.
The status degenerating equipment 53, 63 is composed such that the input reference pixel data 110 is degenerated to the status signal 140 with less bits and is output to the corresponding entropy encoder 52 and entropy decoder 62. A prediction device 54, 64 contains a color order table in its memory for transforming the color pixel data to color order (or reverse of color order) based on the occurrence frequency of each color symbol.
Degeneracy refers to classifying the original status into the number of status after the degeneration. This classification is executed by selecting the combinations such that the entropy (i.e., average information amount to display one symbol) after classification is at a minimum. Moreover, an identification bit is attached to the number of status after degeneration, i.e., after classification. This is the status signal 140.
In one method in which a degeneracy table specifying a relationship between a combined pattern of the color symbol of the reference pixel data 110 and the degeneracy data is established as a degeneracy table to be used in the status degenerating equipment 53, 63. The degeneracy table is used to transform and output the combination pattern of the color symbol of the reference pixel data being input as degenerated data.
FIGS. 20(A)-(B) show an example of a degeneracy operation using such method. For simplicity, an example of a Markov model created by three pixels A, B, C for encoding target pixel X is used as a reference pixel pattern.
If the reference pixel pattern includes three pixels as in FIG. 20 (A), the combination pattern of the color symbol has five possibilities as shown in FIG. 20 (B). In other words, patterns are classified into five patterns, namely a pattern in which all the color symbols of three pixels coincide, three patterns in which only two color symbols coincide and a pattern in which color symbols of all three pixels are different.
Using the FIG. 20(B) table as a degeneracy table of status degenerating equipment 53, 63, the 2.sup.12 patterns which are the number of possible combinations of the original three pixels is degenerated to five status S1-S5 as shown in FIG. 20(B). As a result, the reference pixel data 110 is effectively degenerated and the number of status of the entropy encoder 52 and the entropy decoder 62 is substantially reduced.
A method for such arithmetic encoding and decoding is already disclosed in one pixel encoding standard JBIG (International Standard ISO/IEC 11544), pp. 26-44 and pp. 44-50, the subject matter of which is incorporated herein by reference.
An example of an arithmetic encoding type entropy encoder 52 (FIG. 16) is shown in FIG. 21. The structure of an arithmetic decoding type entropy decoder 62 is substantially the same as the structure of the entropy encoder 52.
The entropy encoder 52 contains an arithmetic algorithm unit 55 and an occurrence probability generation device 56 which functions as a status memory. A status parameter table needed for determining symbol generation probability to be used for encoding is in the occurrence probability generation device 56. The status parameter is specified by the input status symbol. Moreover, the occurrence probability algorithm parameter of the occurrence probability generation device 56 is output to the arithmetic algorithm unit 55 for the table of the status parameter specified by the status symbol. Based on the input occurrence probability, the arithmetic algorithm unit 55 executes entropy encoding and transforms and outputs the color order data 120 as encoding data 200. Moreover, the arithmetic algorithm unit 55 computes the occurrence probability for the status symbol using the value of encoded color order 120, and inputs an algorithm update value to the occurrence probability generation device 56. Storing of the update result as occurrence probability of the next date improves the compression efficiency of the entropy encoder 52.
In order to generate the color order table 120, a color order table is arranged in the prediction devices 54, 64 as described above. FIGS. 23(A)-(C) are an example of an well known color table (see Japanese Laid-Open Patent Publication 6-276041). In determining the color order table for the encoding target pixel X, two-dimensional perimeter data R0, R1, R3, R3 are used as upper color order data, and a one-dimensional table in the same line as the encoding target pixel X is used as lower color order data. First, the color symbols of the perimeter pixel data R0, R1, R2, R3 are deleted from the one-dimensional table, then the upper color order and lower color order are combined to form a color order table of the target pixel X.
The process of forming the color order table is shown in FIGS. 23(A)-(C). A case in which the color symbols are to be encoded will be described. When the color order is fixed by the position of each pixel R0, R1, R2, . . . R8 . . . as shown in FIG. 23(A) and each color symbol becomes C4, C3, C6, C5, C2, C2 . . . as shown in FIG. 23(B), the resulting color table, which is the latest appearance table, becomes the table shown in FIG. 23(C). In other words, the uppermost line becomes C4 for R0, the second order is C3 for R1, the third order is C6 for R2, the fourth order is C5 for R3, the fifth order is C2 for R4, and the sixth order is C2 for R5. However, because C2 already occurs as well as C4 for R6, the sixth order becomes C0 for R7. In this manner, the color order data from which the colors which are already in upper order (i.e., color symbols that appear in R0-R3) is added to the data of R0-R3 and the first to 16th of 16 color symbols are determined. The upper four perimeter pixels may be made variable through learning.
To create the color order table used for transformation of two-dimensional color order shown in FIG. 23, a deleting operation to delete color symbols overlapping in the two-dimensional perimeter data and the one-dimensional table becomes necessary. The process of deleting overlapping color symbols from the one-dimensional table involves vast amounts of processing when the number of bits of the color symbol index code increases. If the total number of color symbols is 16, or equivalently if 4 bits is sufficient for the index code, the process of searching the overlapping color symbols and deleting from the color symbols from the one-dimensional table is not much burden, but if the index code becomes 8 bits then the total number of color symbols becomes 256. Then, the process of searching and deleting overlapping color symbols become enormous.
If the colors of the perimeter pixel data R0, R1, R2 R3 are all different, each color is searched from 256 colors in the one-dimensional table in order to delete whenever the same color symbol is found and to move up the subsequent order with the last color symbol being assigned to the 256th order. To accomplish this, up to 256.times.4 comparisons may be made.
Moreover, in a color order table comprising only the one-dimensional table (including the color order table shown in FIG. 23) or the one-dimensional table shown in FIG. 45 of Japanese Laid-Open Patent Publication 6-276041, a latest appearance table is created or a move-to-front process is executed using a FIFO having a plurality of registers. The amount of processing for creating the latest appearance table increases due to an increase in the amount of algorithm caused by an increase in number of bits in the index code. In dealing with the index codes with large numbers of bits, the process speed declines during multi-color image encoding or decoding.
Moreover, in drastically reducing the status numbers to execute coding and decoding using Markov model reference pixel such as shown in FIG. 20, the context of Markov model input to the entropy encoder 52 and the entropy decoder 62 cannot be verified until the pixels described by A is established in the reference pixels which is one pixel before the encoding target pixel X in FIG. 20 (A). Hence, encoding and decoding must be delayed until the context is confirmed which restricts high speed operation.